#include <iostream>

/*
The eight queens puzzle is the problem of placing eight chess queens on an 8*8 
chessboard so that no two queens attack each other. Thus, a solution requires 
that no two queens share the same row, column, or diagonal. The eight queens 
puzzle is an example of the more general n-queens problem of placing n queens 
on an n chessboard, where solutions exist for all natural numbers n with the 
exception of 2 and 3.

*/

using namespace std;

#define N 8

// print out the solution
void PrintSolution(int queenList[])
{
    for (int i=1; i<=N; i++)
    {
        cout<<queenList[i]<<" ";
    }

	cout << endl;
}

// is it safe to put a queen at position (col, row) based on the current queenList
bool IsSafe(int queenList[], int col, int row)
{
    for (int tempCol = 1; tempCol < col; tempCol++)
    {
		// no need to check tempCol == col as we know they won't be same
        if ( queenList[tempCol] == row ||   // same row
			 col-tempCol == abs(queenList[tempCol] - row)) // diagonal 
		{
			return false;
		}
    }

    return true;
}

// found solution
void PlaceQueen(int col, int queenList[], int &sum)
{
	if (col > N) // found the solution
    {
        sum++;
		PrintSolution( queenList );
		return;
    }

    for( int row=1; row<=N; row++ )
    {
    	if(IsSafe(queenList, col, row))
        {
	        queenList[col] = row;
            PlaceQueen(col+1, queenList, sum); // look for next col
            // no need to reset queenList[col] as the next iteration in the loop 
			// still use the same col, and IsSafe() only check the column less than
			// col, thus all the following columns settings are overwritten
        }
    }
	return;
}

int main()
{
    int queenList[N+1] = {0};
	int sum = 0;

    PlaceQueen(1, queenList, sum);

    cout << "Find "<<sum<<" solutions." << endl;

    cout << "Press any key to exit... " ;
    return getchar();
}